package com.fe.class04;

import java.util.Arrays;

/**
 * @Description 求数组中的大两倍数的数量
 * 在一个数组中，对于每个数num，求后面有多少个数 * 2 依然<num，求总个数
 * @Author sosuke :-)
 * @Date 2021/12/20 06:06
 */
public class Code05_BiggerThanRightTwice {

    public static int biggerThanTwice(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    private static int process(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        return process(arr, L, mid) + process(arr, mid + 1, R) + merge(arr, L, mid, R);
    }

    private static int merge(int[] arr, int L, int mid, int R) {
        int ans = 0;
        // 目前囊括进来的数，是从[M+1, windowR)
        int windowR = mid + 1;
        for (int i = L; i <= mid; i++) {
            while (windowR <= R && ((arr[windowR] << 1) < arr[i])) {
                windowR++; // 满足条件就右移，如果全部满足，则windowR = R+1
            }
            // arr[windowR]是不满足条件的，满足条件的是[M+1, windowR)
            ans += windowR - mid - 1;
            // for (int j = mid + 1; j <= R; j++) {
            //     // 右组中arr[mid + 1...j - 1] 满足条件
            //     if ((arr[j] << 1) >= arr[i]) {
            //         ans += (j - mid -  1);
            //         break;
            //     }
            //     // 右组全部满足条件
            //     if (j == R) {
            //         ans += (j - mid);
            //     }
            // }
        }

        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = mid + 1;
        // 两个指针都没越界
        while (p1 <= mid && p2 <= R) {
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        // p2越界
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        // p1越界
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            arr[L + j] = help[j];
        }
        return ans;
    }

    // for循环方式计算大于二倍数的数量
    public static int comparator(int[] arr) {
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > (arr[j] << 1)) {
                    ans++;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int testTimes = 10000;
        int maxValue = 100;
        int maxSize = 10;
        for (int i = 0; i < testTimes; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            int res1 = biggerThanTwice(arr1);
            int res2 = comparator(arr2);
            if (res1 != res2) {
                System.out.println("Fuck");
                System.out.println("arr1 = " + Arrays.toString(arr1));
                System.out.println("arr2 = " + Arrays.toString(arr2));
                System.out.println("res1 = " + res1);
                System.out.println("res2 = " + res2);
                return;
            }
        }
        System.out.println("Nice");
        int[] arr1 = generateRandomArray(maxSize, maxValue);
        System.out.println("arr1 = " + Arrays.toString(arr1));
        int res1 = biggerThanTwice(arr1);
        System.out.println("res1 = " + res1);
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            // arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
            arr[i] = (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }
}
